package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/11 11:46
 * https://leetcode.cn/problems/open-the-lock/
 */
public class Title752 {

    private static String start = "0000";

    public static int openLock(String[] deadends, String target) {
        if (target.equals(start)) {
            return 0;
        }
        Set<String> deadWords = new HashSet<>();
        deadWords.addAll(Arrays.asList(deadends));
        if (deadWords.contains(start)) {
            return -1;
        }
        LinkedList<String> queue = new LinkedList<>();
        queue.offer(start);
        Map<String, Integer> switchGraph = new HashMap<>();
        switchGraph.put(start, 0);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String password = queue.poll();
                if (password.equals("1200")) {
                    System.out.println();
                }
                Integer times = switchGraph.get(password);
                for (int j = 0; j < password.length(); j++) {
                    char[] chars = password.toCharArray();
                    //每次只能转动一位
                    char[] arr = new char[2];
                    if (chars[j] >= '1' && chars[j] <= '8') {
                        arr[0] = (char) (chars[j] + 1);
                        arr[1] = (char) (chars[j] - 1);
                    } else if (chars[j] == '0') {
                        arr[0] = '9';
                        arr[1] = '1';
                    } else {
                        //9
                        arr[0] = '8';
                        arr[1] = '0';
                    }
                    for (int k = 0; k < 2; k++) {
                        chars[j] = arr[k];
                        String s = String.valueOf(chars);
                        if (s.equals(target)) {
                            return times + 1;
                        }
                        if (!deadWords.contains(s) && !switchGraph.containsKey(s)) {
                            queue.offer(s);
                            switchGraph.put(s, times + 1);
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String[] deadWords = {"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";
        openLock(deadWords, target);
        char c = '1';
        System.out.println(--c);
    }
}
